/*
 *  Universidad del Valle de Guatemala
 *  Algoritmos y Estructura de Datos
 *  Hoja de Trabajo #7
 *  David Ytzen Hsieh Lo #08225
 *
 */
public class Grafo<E> implements InterfazGrafo<E>{
    private final int LIMITE = 20;
    private final int INFINITO = 999999;
    private Nodo nodos[];
    private int arcos[][];
    private int cantNodos;
    private int cantArbol;
    private costoPadre camino[];
    private int nodoActual;
    private int costo;

    public Grafo() {
        
        nodos = new Nodo[LIMITE];
        arcos = new int[LIMITE][LIMITE];
        cantNodos = 0;
        cantArbol = 0;
        for(int i = 0; i < LIMITE; i++)
            for(int j = 0; j < LIMITE; j++)
                arcos[i][j] = INFINITO;
        camino = new costoPadre[LIMITE];



    }

    public void nuevoNodo(E contenido) {
        nodos[cantNodos++] = new Nodo(contenido);
    }

    public void nuevoArco(int inicio, int fin, int costo) {
        arcos[inicio][fin] = costo;
    }

    public void camino() {
        int inicio = 0;
        nodos[inicio].enArbol = true;
        cantArbol = 1;

        for(int i=0; i<cantNodos; i++) {
            int costoTemp = arcos[inicio][i];
            camino[i] = new costoPadre(inicio, costoTemp);
            
        }

        while(cantArbol < cantNodos) {
            int minIndex = caminoMinimo();
            int minimo = camino[minIndex].costo;

            if(minimo == INFINITO) {
                System.out.println("Existen nodos inalcanzables");
                break;
            }
            else {
                nodoActual = minIndex;
                costo = camino[minIndex].costo;
                
            }

            nodos[nodoActual].enArbol = true;
            cantArbol++;
            ajustarCamino();


        }
    }

    public int caminoMinimo() {
        int minimo = INFINITO;
        int minIndex = 0;
        for(int i = 1; i < cantNodos; i++) {
            if(!nodos[i].enArbol && camino[i].costo < minimo) {
                minimo = camino[i].costo;
                minIndex = i;
            }
        }

        return minIndex;
    }

    public void ajustarCamino() {
        int columna = 1;
        while(columna < cantNodos) {
            if(nodos[columna].enArbol) {
                columna++;
                continue;
            }

            int actualArco = arcos[nodoActual][columna];
            int inicioArco = costo + actualArco;
            int costoCamino = camino[columna].costo;

            if(inicioArco < costoCamino) {
                camino[columna].padre = nodoActual;
                camino[columna].costo = inicioArco;
            }

            columna++;
        }
    }

    public void despliegarCaminos() {
        for(int i=0; i < cantNodos; i++) {
            System.out.print(nodos[i].contenido + " = ");
            if(camino[i].costo == INFINITO)
                System.out.print("Infinito");
            else
                System.out.print(camino[i].costo);
            E padre = (E) nodos[camino[i].padre].contenido;
            System.out.print(" desde " + padre.toString() + "\n");
        }
        System.out.println("");
    }
    
}
